package ljl.codetop300;

import commons.TreeNode;

/**
 * 我还想着左旋右旋，其实不用
 * 我看那么多代码有个屁用啊
 * 出来混要有实力，要有背景
 */
public class _450_delete_node {

  static class off_1 {
    public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) {
        return null;
      }
      if (root.val > key) {
        root.left = deleteNode(root.left, key);
        return root;
      }
      if (root.val < key) {
        root.right = deleteNode(root.right, key);
        return root;
      }
      if (root.left == null && root.right == null) {
        return null;
      }
      if (root.right == null) {
        return root.left;
      }
      if (root.left == null) {
        return root.right;
      }
      TreeNode successor = root.right;
      while (successor.left != null) {
        successor = successor.left;
      }
      successor.right = deleteNode(root.right, successor.val);
      successor.left = root.left;
      return successor;
    }
  }

  static class copy_off_1 {
    public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) return null;
      if (root.val < key) {
        root.right = deleteNode(root.right, key);
        return root;
      }
      if (root.val > key) {
        root.left = deleteNode(root.left, key);
        return root;
      }
      if (root.left == null && root.right == null) {
        return null;
      }
      if (root.left == null) return root.right;
      if (root.right == null) return root.left;
      TreeNode suc = root.right;
      while (suc.left != null) {
        suc = suc.left;
      }
      suc.right = deleteNode(root.right, suc.val);;
      suc.left = root.left;
      return suc;
    }
  }

  static class off_2 {
    public TreeNode deleteNode(TreeNode root, int key) {
      TreeNode cur = root, curParent = null;
      while (cur != null && cur.val != key) {
        curParent = cur;
        if (cur.val > key) {
          cur = cur.left;
        } else {
          cur = cur.right;
        }
      }
      if (cur == null) {
        return root;
      }
      if (cur.left == null && cur.right == null) {
        cur = null;
      } else if (cur.right == null) {
        cur = cur.left;
      } else if (cur.left == null) {
        cur = cur.right;
      } else {
        TreeNode successor = cur.right, successorParent = cur;
        while (successor.left != null) {
          successorParent = successor;
          successor = successor.left;
        }
        if (successorParent.val == cur.val) {
          successorParent.right = successor.right;
        } else {
          successorParent.left = successor.right;
        }
        successor.right = cur.right;
        successor.left = cur.left;
        cur = successor;
      }
      if (curParent == null) {
        return cur;
      } else {
        if (curParent.left != null && curParent.left.val == key) {
          curParent.left = cur;
        } else {
          curParent.right = cur;
        }
        return root;
      }
    }
  }

  /**
   * 极度不推荐迭代法
   * 情况太多了
   */
  static class copy_off_2 {
    public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) return null;
      TreeNode parent = null;
      TreeNode cur = root;
      while (cur != null && cur.val != key) {
        parent = cur;
        if (cur.val > key) {
          cur = cur.left;
        } else {
          cur = cur.right;
        }
      }
      if (cur == null) return root;
      if (cur.left == null && cur.right == null) cur = null;
      else if (cur.left == null) cur = cur.right;
      else if (cur.right == null) cur = cur.left;
      else {
        TreeNode suc = cur.right;
        TreeNode sucParent = cur;
        while (suc.left != null) {
          sucParent = suc;
          suc = suc.left;
        }
        if (sucParent == cur) {
          sucParent.right = suc.right;
        } else {
          sucParent.left = suc.right;
        }
        suc.left = cur.left;
        suc.right = cur.right;
        cur = suc;
      }
      if (parent == null) return cur;
      if (parent.left != null && parent.left.val == key) {
        parent.left = cur;
      } else {
        parent.right = cur;
      }
      return root;
    }
  }
}
